package com.example.java.yugutou.chapter1_linklist.level1;

/**
 * @Author : 佩萁
 * Description :
 * @Create : 2023/11/29 - 14:13
 */
public class CrudLinkList {
    public static void main(String[] args) {
        int[] a = {1, 2, 3, 4, 5, 6};
        Node head = initLinkedList(a);//创建链表，返回头指针head
        //在遍历时可以不用再添加给头结点，因为添加虚拟头结点只是针对增加和删除操作而言，防止出现空链表而做特殊处理带来的复杂性
//        Node node = new Node(1);
        System.out.println(display(head));

        //添加结点
        System.out.println("链表长度:" + getLength(head));
        Node node = new Node(0);//创建一个结点
        head = insertNode(head, node, 7);//插入结点并且重新赋给head，获得新的链表
        System.out.println("链表长度:" + getLength(head));
        System.out.println(display(head));

        //删除结点
        head = deleteNode(head, 8);
        System.out.println(display(head));
    }

    //创建结点方法
    static class Node {
        final int data;//数据域
        Node next;//指针域

        Node(int data) {
            this.data = data;
        }
    }

    //遍历链表方法
    public static String display(Node head) {
        //将头指针赋值给新创建的结点，这样我们就可以顺着头结点依次找到后面的结点了
        Node current = head;
        //StringBuffer是线程安全的
        StringBuffer sb = new StringBuffer();
        //如果当前的结点不为空，就进入循环体
        while (current != null) {
            //既然不为空已经进入了循环体，说明当前节点是有数据的，将数据存放进StringBuffer
            sb.append(current.data).append("\t");
            current = current.next;//将当前节点的指针移向下一位
        }
        return sb.toString();//将sb里的数据展示出来
    }

    /**
     * 链表插入数据
     *
     * @param head       链表头结点
     * @param nodeInsert 待插入结点
     * @param position   待插入位置
     * @return 插入后得到链表的头结点
     */
    public static Node insertNode(Node head, Node nodeInsert, int position) {
        //如果头结点为空，则直接返回要插入的结点就可以
        if (head == null) {
            return nodeInsert;
        }
        //先获取链表长度，然后遍历找到需要插入的位置
        int size = getLength(head);
        //如果要插入的位置超过了链表长度甚至比插入尾部的位置还要大，这个时候就插入失败了
        //如果插入的位置小于链表长度甚至比插入链表头部还要靠前，插入失败
        if (position > size + 1 || position < 1) {
            System.out.println("位置参数越界");
            return head;//插入失败返回本来的head
        }

        //插入头部，就是插入链表第一个位置
        if (position == 1) {
            //让待插入结点next指向原来的头结点就可以
            nodeInsert.next = head;
            //将新插入的结点作为新的头结点
            head = nodeInsert;
            //返回头结点
            return head;
        }
        //插入中间和尾部
        //先初始化一个结点，后面遍历链表会不断移动这个结点
        Node pNode = head;
        //定义一个变量，用来找到要插入的位置的前一位
        int count = 1;
        while (count < position - 1) {
            //不断给pNode换结点，直到找到要插入位置的前一个结点
            pNode = pNode.next;
            count++;
        }
        //流程走到这，已经找到了要插入位置的前一个结点
        //插入的时候，只能先让nodeInsert.next = pNode.next,
        //因为如果先让pNode.next = nodeInsert这个时候原来pNode与其下一个结点的连线就会断开，
        //随后pNode后的结点就会被垃圾回收，这个时候nodeInsert就找不到下一个结点了
        nodeInsert.next = pNode.next;
        pNode.next = nodeInsert;
        return head;//返回插入后的链表头结点
    }

    /**
     * 获取链表长度，Java没有提供封装好的获取链表长度的方法，
     * 对于ArrayList或LinkedList，我们可以使用.size()来获取，对于自定义的链表，我们需要遍历链表获取
     *
     * @param head 链表头结点
     * @return 链表长度
     */
    public static int getLength(Node head) {
        int length = 0;//定义一个变量，用来表示链表长度
        Node node = head;//接收传入的链表头结点
        //如果node不为空，第一次判断是判断头结点是否为空，后面判断的是当前节点是否为空
        while (node != null) {
            length++;
            node = node.next;//向后遍历
        }
        //返回链表长度
        return length;
    }

    static Node initLinkedList(int[] array) {//传入一个数组，数组元素是链表的val值
        //创建头指针和头结点，初始化为空，初始化一个head的目的是不论到哪都能找到这个链表的头，因为这是个单向链表
        Node head = null, cur = null;
        //循环遍历传入的数组来为结点的val赋值
        for (int i = 0; i < array.length; i++) {
            //创建一个尾指针为null，不指向任何结点的结点
            Node newNode = new Node(array[i]);
            //newNode.next = null;
            //如果是遍历数组中第一个位置的，应该让初始化的头指针和头结点赋值个新建的结点newNode
            if (i == 0) {
                //头指针指向第一个新结点，它需要一直保留，所以在下面的else中就不再修改它的值了
                head = newNode;
                cur = newNode;//当前节点为新结点
            } else {//如果i不是0，说明在此之前已经有节点了，需要让前面的结点指向这个新创建的结点
                cur.next = newNode;//当前节点指向新结点
                cur = newNode;//当前节点更新为新结点
            }
        }
        return head;//返回头指针
    }

    /**
     * 删除结点
     *
     * @param head     链表头结点
     * @param position 删除结点位置，取值从1开始
     * @return 删除后的链表头结点
     */
    public static Node deleteNode(Node head, int position) {
        //如果链表头结点为空，说明链表为空，不用删除直接返回
        if (head == null) {
            return null;
        }
        //获得链表长度
        int size = getLength(head);
        //思考一下，这里为什么不是size + 1?
        //删除和插入差别还是挺大的，插入的话可以在一个空位置放结点，
        //而删除，如果这个位置是空的，我们怎么删除呢？
        //所以当要插入的位置大于链表长度就删除失败，当position小于1，是没有结点的，也删除失败
        if (position > size || position < 1) {
            System.out.println("输入的参数有误");
            return head;
        }
        //删除头结点
        if (position == 1) {
            return head.next;//头结点往后移动一位
        } else {
            //头结点给到当前节点
            Node cur = head;
            int count = 1;
            //找要删除结点的前一个结点
            while (count < position - 1) {
                cur = cur.next;
                count++;
            }
            //到此找到了要删除结点的前一个结点
            //把当前节点的下一个结点给到新创建的结点
            Node curNode = cur.next;
            //新创建结点的下一个结点再给到当前节点的下一个，等于说这样就跳过看要删除的结点
            cur.next = curNode.next;
        }
        //返回删除后的链表头结点
        return head;
    }
}
